/**
 * @author ChaP
 * @date 2019/06/01
 * @describe:
 */
package CodingTest.AC20190601;

/**
 * leetcode -473
 * 还记得童话《卖火柴的小女孩》吗？现在，你知道小女孩有多少根火柴，请找出一种能使用所有火柴拼成一个正方形的方法。不能折断火柴，可以把火柴连接起来，并且每根火柴都要用到。

 输入为小女孩拥有火柴的数目，每根火柴用其长度表示。输出即为是否能用所有的火柴拼成正方形。

 示例 1:

 输入: [1,1,2,2,2]
 输出: true

 解释: 能拼成一个边长为2的正方形，每边两根火柴。
 示例 2:

 输入: [3,3,3,3,4]
 输出: false

 解释: 不能用所有火柴拼成一个正方形。
 注意:

 给定的火柴长度和在 0 到 10^9之间。
 火柴数组的长度不超过15。
 */
public class makesquare {
    public boolean makesquare(int[] nums){
        if(nums.length <= 3) return false;
        int sum = 0;
        for(int e:nums){
            sum+=e;
        }
        if(sum%4 != 0) return false;
        int edg = sum/4;
        return helper(nums,0,nums.length,0,0,0,0,edg);
    }
    public boolean helper(int[] nums,int i ,int length,int l1,int l2,int l3,int l4,int e){
        if(i == length){
            if(l1 == e && l2 == e && l3 == e && l4 ==e) return true;
            return false;
        }
        if(l1 > e || l2 > e || l3 > e || l4 >e) return false;
        return helper(nums,i+1,length,l1+nums[i],l2,l3,l4,e)||
                helper(nums,i+1,length,l1,l2+nums[i],l3,l4,e)||
                helper(nums,i+1,length,l1,l2,l3+nums[i],l4,e)||
                helper(nums,i+1,length,l1,l2,l3,l4+nums[i],e);
    }

}
